這題是一個經典的鏈結串列問題，讓我們一起來輕鬆破解兩個鏈結串列的交集點吧！不需要複雜的數學或資料結構，跟著步驟一步步來就能搞定！

160. Intersection of Two Linked Lists

問題敘述 / Problem Statement

英文:

Given the heads of two singly linked lists, headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection, return null.

The lists are structured such that there are no cycles, and their original structures must remain intact after the function returns.

Custom Judge:

The function inputs are indirectly provided:

• intersectVal: The value of the node where the intersection occurs. If there is no intersection, this value is 0.
• listA: The first linked list.
• listB: The second linked list.
• skipA: The number of nodes to skip ahead in listA to reach the intersected node.
• skipB: The number of nodes to skip ahead in listB to reach the intersected node.

The function receives headA and headB and should correctly identify the intersection node or return null.

中文:

給定兩個單向鏈結串列的頭節點 headA 和 headB，返回兩個鏈結串列相交的節點。如果兩個鏈結串列沒有交點，則返回 null。

鏈結串列的結構保證不會形成循環，且在函數返回後必須保留原始結構。

自定義判斷器:

輸入的測試數據通過以下參數間接提供:

• intersectVal: 相交節點的值，如果兩個鏈結串列不相交，則該值為 0。
• listA: 第一個鏈結串列。
• listB: 第二個鏈結串列。
• skipA: listA 中跳過的節點數量，用以抵達相交節點。
• skipB: listB 中跳過的節點數量，用以抵達相交節點。

函數接收 headA 和 headB，需正確識別相交的節點或返回 null。

範例 / Examples

範例 1:

• 輸入: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
• 輸出: 相交於 '8'

說明:

相交節點的值是 8，兩個鏈結串列在值為 8 的節點相交，相交節點指向同一記憶體位置。

Example 1:

• Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
• Output: Intersected at '8'

Explanation:

The intersection node's value is 8. The lists listA and listB have intersected at the node with value 8. The intersecting nodes refer to the same memory location.

範例 2:

• 輸入: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
• 輸出: 相交於 '2'

說明:

相交於值為 2 的節點。

Example 2:

• Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
• Output: Intersected at '2'

Explanation:

The intersection occurs at the node with value 2.

範例 3:

• 輸入: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
• 輸出: 無交集

說明:

兩個鏈結串列沒有相交，應返回 null。

Example 3:

• Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
• Output: No intersection

Explanation:

The lists do not intersect, so the function should return null.

解題思路 / Solution Approach

為了解決這個問題，主要目標是找到兩個鏈結串列之間的交集節點。解題思路包括：

1. 計算長度: 遍歷兩個鏈結串列以確定它們的長度。這使我們能夠找出需要調整哪一個鏈結串列來對齊兩者的起始點。

2. 對齊鏈結串列: 調整較長的鏈結串列的起始位置，使兩個鏈結串列在剩餘節點數量上相等。

3. 同時遍歷: 同時遍歷兩個鏈結串列，通過直接比較節點來檢查是否相交。如果節點相同，即找到交集點。否則，繼續遍歷直到結束。

4. 返回結果: 如果找到交集，則返回相交節點；否則返回 null。

詳細步驟:

1. 計算 listA 和 listB 的長度。
2. 確認哪個鏈結串列較長，然後將其指標前移，使兩者剩餘的節點數量相等。
3. 同時遍歷兩個鏈結串列，找到第一個相同的節點，即為交集點。
4. 如果沒有找到相同的節點，返回 null。

程式碼實現 / Code Implementation

class ListNode {
    val: number;
    next: ListNode | null;

    constructor(val: number, next: ListNode | null = null) {
        this.val = val;
        this.next = next;
    }
}

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    // Edge case: If either list is empty, return null
    if (!headA || !headB) return null;

    // Helper function to calculate the length of a list
    const getLength = (head: ListNode | null): number => {
        let length = 0;
        while (head) {
            length++;
            head = head.next;
        }
        return length;
    };

    // Get lengths of both lists
    let lenA = getLength(headA);
    let lenB = getLength(headB);

    // Align the start of both lists
    while (lenA > lenB) {
        headA = headA.next!;
        lenA--;
    }
    while (lenB > lenA) {
        headB = headB.next!;
        lenB--;
    }

    // Traverse both lists to find the intersection
    while (headA && headB) {
        if (headA === headB) return headA; // Intersection found
        headA = headA.next;
        headB = headB.next;
    }

    // No intersection
    return null;
}

程式碼解釋:

1. getLength 函數用於計算給定鏈結串列的長度。
2. 調整 headA 和 headB 的指標，通過跳過較長鏈結串列的節點，使兩個鏈結串列的長度相等。
3. 同時遍歷兩個鏈結串列，尋找第一個相同的節點，即為交集點。
4. 如果未找到相同的節點，則返回 null。

這個解法的時間複雜度是 O(n + m)，其中 n 和 m 分別是兩個鏈結串列的長度，效率良好。

題型重點 / Key Points for the Problem

1. 問題類型：

   • 判斷兩個單向鏈結串列是否有相交點，並返回交集節點或 null。

2. 鏈結串列的特性：

   • 不存在循環，且在函數返回後必須保持鏈結串列的原始結構不變。

3. 自定義判斷器的參數：

   • intersectVal: 相交節點的值，若無相交節點則為 0。
   • listA: 第一個鏈結串列。
   • listB: 第二個鏈結串列。
   • skipA: listA 中為抵達相交節點所需跳過的節點數量。
   • skipB: listB 中為抵達相交節點所需跳過的節點數量。

4. 解題思路：

   • 計算兩個鏈結串列的長度。
   • 調整較長鏈結串列的起始點，讓兩個鏈結串列剩餘的節點數量相同。
   • 同時遍歷兩個鏈結串列，檢查節點是否相同。
   • 返回相交節點或 null。

5. 程式碼實現的步驟：

   • 使用 getLength 函數計算鏈結串列的長度。
   • 調整 headA 和 headB 的指標，使兩者從相同長度的起點開始遍歷。
   • 同時遍歷兩個鏈結串列，找到第一個相同的節點作為交集點。
   • 若沒有相交節點，返回 null。

6. 程式碼效率：

   • 時間複雜度為 O(n + m)，n 和 m 分別是兩個鏈結串列的長度，具有良好的效率表現。

7. 注意事項：

   • 確保在比較節點時是比較節點的記憶體地址，而不是僅僅比較節點的值。
   • 調整鏈結串列起始點時，必須確保較長鏈結串列的指標先移動，直到兩個鏈結串列的剩餘長度相同。

面對每個難題都像是在挑戰自己的極限呢！
每次解題都是一次小小的突破，成就感滿滿！加油吧，不輕言放棄的人最可愛啦！✨